# wrong answer! 122 and 212 will be treated as two solutions
def coin_change_2(amount, coins):
    # dp = amount+1
    dp = [0] * (amount + 1)
    dp[0] = 1
    for a in range(1, amount + 1):
        dp[a] = sum(dp[a - c] for c in coins if c <= a)
    return dp[amount]


def coin_change_3(amount, coins):
    # dp = (amount+1) * (len(coins)+1)
    coin_no = len(coins)
    dp = [[0] * (coin_no + 1) for _ in range(amount + 1)]
    for i in range(amount + 1):
        for j in range(coin_no + 1):
            # base
            if i == 0 and j == 0:
                dp[i][j] = 1
            # current coin not allowed + current coin allowed
            else:
                dp[i][j] = dp[i][j - 1] + dp[i - coins[j - 1]][j] if i >= coins[j - 1] else dp[i][j - 1]
    return dp[amount][coin_no]

print(coin_change_2(5, [1, 2, 5]))
print(coin_change_3(5, [1, 2, 5]))
